# 递归会导致大量的重复计算，可以使用记忆化搜索优化它
def fib_memo(n,memo={}):
    if n <= 1:
        return n
    if n not in memo:
        memo[n] = fib_memo(n-1,memo)+fib_memo(n-2,memo)
    return memo[n]

if __name__ == "__main__":
    n = int(input("Enter a number: "))
    print(f"The {n}th Fibonacci number is: {fib_memo(n)}")
# 这个版本使用了一个字典来存储已经计算过的 Fibonacci 数字，从而避免了重复计算